\section{Metaheurísticas}
Las metaheurísticas pueden definirse como 
 métodos diseñados para encontrar buenas soluciones a problemas de optimización
combinatoria en general. La idea de su uso surge cerca de la década del 80 y son
en cierto sentido más generales que los métodos heurísticos tradicionales aunque
pueden utilizar a los mismos dentro de sus implementaciones. En comparación con otros
 métodos de optimización, las metaheurísticas no garantizan que una solución óptima sea
encontrada ya que generalmente las implementaciones dependen de algoritmos
estocásticos basados en un conjunto de variables que se generan de forma
aleatoria. Sin embargo, generalmente las metaheurísticas suelen
 generar buenas aproximaciones a la solución de los problemas utilizando menor
 esfuerzo de procesamiento que otros métodos y por consiguiente alcanzan estas
 buenas aproximaciones en un tiempo más corto.\\

Existe una gran variedad de metaheurísticas y, tanto los desarrollos como los
diseños de las mismas, suelen estar motivados por comportamientos naturales que
aparecen en diversos campos como la biología, la física, entre otras
disciplinas. Existen múltiples maneras de clasificarlas, una de ellas es según
las estrategias de búsqueda. Un primer tipo se basa en mejoras aplicadas sobre 
algoritmos de búsqueda local como
por ejemplo Simmulated Annealing, Tabu Search y GRASP entre otros. Otro son
aquellos donde la estrategia de búsqueda involucra un componente de aprendizaje
tal como Colonia de Hormigas y los Algoritmos Genéticos. Otra forma de
clasificarlas es según si la búsqueda está basada en una única solución
o en una población de soluciones. Aquellas que utilizan una única solución se
enfocan en mejorar y modificar una única solución candidata hasta alcanzar un
objetivo como pueden ser Simmulated Annealing y Variable Neighborhood Search.
Las que utilizan una población, mantienen y mejoran múltiples soluciones
candidatas y suelen utilizar propiedades propias de la población para guiar la
búesqueda. Dentro de este grupo se puede encontrar a los Algoritmos Genéticos y
la Computación Evolutiva.\\

Además de las metaheurísticas mencionadas anteriormente, existen las denominadas
híbridas y las denominadas pararelas. Los algoritmos híbridos son aquellos que
combinan una metaheurística con otro método de aproximación, como puede ser Constraint
Programming o incluso otra metaheurística. Ambos componentes pueden ejecutarse
en simultaneo o uno embebido dentro del otro e intercambiar información para
guiar la búsqueda. Los algoritmos paralelos son aquellas que utilizan
técnicas de programación en paralelo o distribuida para ejecutar múltiples
búsquedas en paralelo. Pueden variar desde simples esquemas distribuidos hasta
búsquedas concurrentes que interactuan entre si para mejorar una solución
general.


\subsection{Algoritmos Evolutivos}

Los algoritmos evolutivos (\textit{EA}) \cite{Zbigniew} surgen cerca de la
década del cincuenta y si bien pueden ser utilizados para diversos propósitos, se los emplea
frecuentemente con el fin de resolver
problemas de optimización. Estos se basan en los principios de la evolución biológica formulados por Darwin.\\

Los EA consisten en generar conjuntos de posibles soluciones del problema en
cuestión que irán evolucionando iterativamente con la esperanza de que los
nuevos conjuntos contengan soluciones mejores a las anteriores. En el contexto de los
EA, a estos conjuntos se los denomina
\textit{poblaciones} y a cada una de las soluciones se las denomina
\textit{individuo}.
Para medir la calidad de un individuo, es decir, la calidad de una solución, se
utiliza una función de evaluación (\textit{fitness}).
Esta función se calcula teniendo en cuenta el o los objetivos que se quieran cumplir en cada uno de los individuos. 
Su complejidad se desprende del dominio del problema, de el o los objetivos y del modelo que se
haya utilizado para representar a los individuos. El mapeo entre una solución
real y un indiviuo puede variar según el problema yendo desde un simple número
hasta una estructura compleja.\\
 
En cada uno de los ciclos del algoritmo se seleccionan algunos individuos
de la población y, mediante operaciones, se los combina o transforma
para dar origen a nuevos individuos (\textit{offsprings}). Estos individuos
llevan información de sus padres pero no necesariamente son mejores respecto a su
fitness. La búsqueda de diversidad en la población se utiliza para no caer de
forma temprana en máximos locales. Una vez generados los
individuos descendientes, se juntan con sus padres y con el resto de la
población para obtener entonces la próxima generación. Los criterios de parada del algoritmo pueden ser diversos: tiempo,
diversidad de la población, valor de fitness, entre otros.\\ 

La implementación y parametrización del criterio de
parada, junto con el tamaño de la población, las estrategias de selección y
reemplazo, las operaciones entre individuos, la función de evaluación,
etc, son de gran importancia y definen el comportamiento del
algoritmo. Tienen siempre presentes en sus implementaciones cierto grado
de aleatoriedad lo que convierte a estos algoritmos en no determínísticos.\\

\noindent El siguiente pseudocódigo resume el comportamiento de ésta clase de
algoritmos:\\

\begin{algorithm}
\begin{algorithmic}[1]
\STATE $poblacion \gets$ generar una población inicial de individuos
\STATE evaluar el fitness de cada individuo de la $poblacion$
\WHILE {algun criterio de parada}
	\STATE 	$padres \gets$ seleccionar individuos de $poblacion$
	\STATE	$hijos \gets$ generar individuos a partir de operaciones geneticas
	sobre $padres$
	\STATE	evaluar el fitness de cada individuo en $hijos$
	\STATE	$poblacion \gets$ crear una nueva poblacion a partir de $poblacion$ e
	$hijos$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

Los algoritmos evolutivos suelen clasificarse en cuatro grandes grupos según los
detalles de implementación y la naturaleza de los problemas en los que aplican, 
aunque en la práctica es común encontrar implementaciones que combinan sus
ca\-rac\-te\-rís\-ti\-cas:
\begin{description}
\item[Algoritmos Genéticos] Principalmente utilizados para resolver problemas de
optimización. Las soluciones suelen representarse como una cadena de bits y las
operaciones clásicas son la mutación y la recombinación de individuos.
\item[Programación Genética] Suele utilizarse en inteligencia artificial. Las
soluciones suelen ser programas y sus fitness se calculan resolviendo algún
problema.
\item[Programación Evolutiva] Similar a programación genética pero en lugar de
evolucionar la estructuras de los programas evolucionan sus parámetros.
\item[Estrategias Evolutivas] Tienen como particularidad que adaptan sus
parámetros en tiempo de ejecución.
\end{description}
 
\subsection{Algoritmos Genéticos}
Los algoritmos genéticos (\textit{GA}) son los utilizados con mayor frencuencia
dentro de la familia de los algoritmos evolutivos. Suelen aplicarse a problemas de
optimización combinatoria. En estos algoritmos, los individuos, que son
denominados \textit{cromosomas}, son representados generalmente por cadenas
binarias de longitud fija aunque la representación puede variar dependiendo del problema. 
A cada parte o atributo de un cromosoma se lo denomina \textit{gen}. 
Las operaciones que dan lugar a nuevos cromosomas son la \textit{mutación} y
el \textit{cruzamiento} (\textit{crossover}) y ambas operaciones crean nuevos
cromosomas, modificando o cruzando los genes de sus padres.

\begin{description}
\item[Mutación] Consiste en la alteración de uno o varios genes del cromosoma y
se utiliza principalmente para mantener la diversidad en la población. Su idea
se basa en la mutación biológica. El ejemplo más claro es la alteración de un
bit en una representación binaria de un cromosoma:\\

\begin{center}
\begin{tabular}{c c c c c}
1&0&0&1&0\\
 & &$\downarrow$& & \\
1&0&1&1&0\\ 
\end{tabular}
\end{center}

\item[Crossover] Análogo a la reproducción biológica y crossover biológico, 
consiste en tomar más de una solución padre y generar a partir de ellas, uno o
más cromosomas hijos mediante el cruzamiento de genes. Existen varias técnicas y
dependen entre otras variables de la estructura que se haya elegido para la
representación del individuo. Ejemplo de crossover en un punto sobre cadenas de bits:
\begin{center}
\begin{tabular}{l|c c c c c}
\multirow{3}{*}{Padres} &(1&1)&0&1&0\\
						&1&0&(0&0&1)\\
\hline
\multirow{3}{*}{Hijos} 	&(1&1&0&0&1)\\
						&1&0&0&1&0\\
\end{tabular}
\end{center}

\end{description}

En los GA, en cada iteración se selecciona un número de candidatos de la
población que serán luego utilizados para crear la nueva generación mediante
las operaciones genéticas. Con el objetivo de seleccionar en mayor
proporción los cromosomas de buena calidad suelen utilizarse
estrategias que involucran el fitness. Entre las más utilizadas se encuentran
\textit{Roulette Wheel Selection} y \textit{Tournament Selection}. 
La primera simula ser una rueda de ruleta, donde los individuos de mayor fitness tienen
mayor probabilidad de ser elegidos. En la segunda estrategia, se arman
pequeños grupos de individuos y se los hace competir entre sí, resultando
seleccionado el ganador de la competencia.\\

Para la creación de nuevas generaciones, es decir, la creación de una nueva
población a partir de los nuevos y viejos individuos, suelen utilizarse
estrategias de elitismo. Estas estrategias permiten mantener las soluciones de
buena calidad a lo largo de las distintas generaciones. Las poblaciones
iniciales de estos tipos de algoritmos son comunmente generadas de manera
aleatoria aunque pueden implementarse mejoras.

\subsection{Búsqueda Local}
Las búsquedas locales son métodos metaheurísticos de optimización que, a
di\-fe\-ren\-cia de los anteriores, parten de una única solución e iteran
reiteradamente re\-a\-li\-zan\-do modificaciones sobre la misma. Más
precisamente, éstos métodos comienzan con una solución candidata a un problema
determinado y reiteradamente se mueven bajo algún criterio de optimización a una solución vecina hasta cumplir
con algún objetivo de terminación.\\

Por lo general, una solución candidata tiene más de una solución vecina. A este
conjunto de soluciones vecinas se lo denomina vecindario. La elección de esa solución 
vecina se realiza utilizando información exclusivamente del vecindario de la
solución candidata, de ahí el nombre de búsqueda local. En el caso que el
criterio de elección consista en tomar siempre al mejor de todos los posibles
vecinos, al método se lo denomina \textit{Hill Climbing} \cite{Luke}.  Cuando no
existen mejoras entre las soluciones del vecindario, se dice que el método se encuentra con una
solución localmente óptima.\\

\noindent El siguiente pseudocódigo resume el comportamiento de esta clase de
algoritmos:\\

\begin{algorithm}
\begin{algorithmic}[1]
\STATE $solucionCandidata \gets$ Armar u obtener la solucion a mejorar
\WHILE {algún criterio de parada}
	\STATE 	$vecinos \gets$ buscar las soluciones vecinas de $solucionCandidata$
	\STATE	$solucionCandidata \gets$ seleccionar vecino bajo algún criterio de
	$vecinos$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

